package leetcode.code0842;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;

public class Solution implements IDebug {

	int len;

	public List<Integer> splitIntoFibonacci(String num) {
		len = num.length();
		int[] nums = new int[len];
		char[] cs = num.toCharArray();
		for (int i = 0; i < cs.length; i++) {
			nums[i] = cs[i] - '0';
		}
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < Math.min(32, len); i++) {
			int num1 = this.num(nums, 0, i);
			if (num1 == -1) {
				continue;
			}
			for (int j = i + 1; j < Math.min(i + 33, len); j++) {
				int num2 = this.num(nums, i + 1, j);
				if (num2 == -1) {
					continue;
				}
				list.add(num1);
				list.add(num2);
				if (this.splitIntoFibonacci(nums, num1, num2, j + 1, list)) {
					return list;
				}
				list = new ArrayList<>();
			}
		}
		return list;
	}

	private boolean splitIntoFibonacci(int[] nums, int num1, int num2, int index, List<Integer> list) {
		if (index == len) {
			return list.size() > 2;
		}
		long num = num1 * 1L + num2;
		if (num >= Integer.MAX_VALUE) {
			return false;
		}
		int com = 0;
		for (int i = index; i < len; i++) {
			com = com * 10 + nums[i];
			if (com > num) {
				return false;
			}
			if (com == num) {
				list.add(com);
				return this.splitIntoFibonacci(nums, num2, com, i + 1, list);
			}
		}
		return false;

	}

	private int num(int[] nums, int L, int R) {
		long ans = 0;
		if (nums[L] == 0 && R != L) {
			return -1;
		}
		for (int i = L; i <= R; i++) {
			ans = ans * 10 + nums[i];
		}
		return ans >= Integer.MAX_VALUE ? -1 : (int) ans;
	}

	@Override
	public void debug4() {
		this.splitIntoFibonacci(
				"539834657215398346785398346991079669377161950407626991734534318677529701785098211336528511");
		this.splitIntoFibonacci("123456579");

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

//	[539834657,21,539834678,539834699,1079669377,1619504076,-1595793843,23710233,-1572083610,-1548373377]
	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		System.out.println(1 << 31);
		System.out.println(1619504076 + 1079669377);
	}

}
